package com.itheima.leetcode.od.b.binary;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;

/**
 * (B卷,100分)- 事件推送（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 同一个数轴X上有两个点的集合A={A1, A2, …, Am}和B={B1, B2, …, Bn}，Ai和Bj均为正整数，A、B已经按照从小到大排好序，
 * <p>
 * A、B均不为空，给定一个距离R(正整数)，列出同时满足如下条件的所有（Ai, Bj）数对：
 * <p>
 * Ai <= Bj
 * Ai, Bj之间的距离小于等于R
 * 在满足1,2的情况下,每个Ai只需输出距离最近的Bj
 * 输出结果按Ai从小到大的顺序排序
 * <p>
 * 输入描述
 * <p>
 * 第一行三个正整数m,n,R
 * <p>
 * 第二行m个正整数,表示集合A
 * <p>
 * 第三行n个正整数,表示集合B
 * <p>
 * 输入限制：
 * <p>
 * 1<=R<=100000, 1<=n,m<=100000, 1<=Ai,Bj<=1000000000
 * <p>
 * 输出描述
 * <p>
 * 每组数对输出一行Ai和Bj,以空格隔开
 * <p>
 * 用例
 * <p>
 * 输入	4 5 5
 * 1 5 5 10
 * 1 3 8 8 20
 * 输出	1 1
 * 5 8
 * 5 8
 * 说明	无
 */
public class EventPush {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        Integer[] tmp = Arrays.stream(sc.nextLine().split(" "))
                .map(Integer::parseInt)
                .toArray(Integer[]::new);

        int m = tmp[0];
        int n = tmp[1];
        int r = tmp[2];

        Integer[] a = Arrays.stream(sc.nextLine().split(" "))
                .map(Integer::parseInt)
                .toArray(Integer[]::new);

        Integer[] b = Arrays.stream(sc.nextLine().split(" "))
                .map(Integer::parseInt)
                .toArray(Integer[]::new);*/

        String input1 = "4 5 5";
        Integer[] tmp = Arrays.stream(input1.split(" "))
                .map(Integer::parseInt)
                .toArray(Integer[]::new);

        int m = tmp[0];
        int n = tmp[1];
        int r = tmp[2];

        String input2 = "1 5 5 10";
        Integer[] a = Arrays.stream(input2.split(" "))
                .map(Integer::parseInt)
                .toArray(Integer[]::new);

        String input3 = "1 3 8 8 20";
        Integer[] b = Arrays.stream(input3.split(" "))
                .map(Integer::parseInt)
                .toArray(Integer[]::new);

        System.out.println(getResult(r, a, b));
    }

    public static String getResult(int r, Integer[] a, Integer[] b) {
        ArrayList<String> list = new ArrayList<>();
        for (int ai : a) {
            int j = Arrays.binarySearch(b, ai);

            // 如果在b数组中可以找到ai，则此时j就是ai在b数组中的位置，此时ai和bj是满足要求，且最接近的
            if (j >= 0) {
                list.add(ai + " " + b[j]);
            } else {
                // 如果在b数组中找不到ai，则此时j就是ai在b数组中有序插入位置-insertIdx-1，
                // 因此insertIdx = -j-1，此时b[insertIdx]满足大于ai，我们只需要检查b[insertIdx] - ai<=r即可
                int insertIdx = -j - 1;
                // 有序插入位置可能是越界位置
                if (insertIdx == b.length) {
                    continue;
                }
                if (b[insertIdx] - ai <= r) {
                    list.add(ai + " " + b[insertIdx]);
                }
            }
        }

        return list.stream().collect(Collectors.joining("\n"));
    }
}